Present invention embodiments relate to compression and storage of data, and more specifically, to composing compression nodes to achieve hierarchical compression of data and manipulating the compression hierarchy to defer or reduce computation during query evaluation.
Good compression ratios are needed in order to maximize capacity of storage and caches as well as reduce the amount of data traffic (e.g., input/output (I/O)) during query evaluations on storage and data networks. Existing compression schemes generally require full decompression (either to a buffer or streaming) before the data may be operated on as part of the query evaluation. Central processing unit (CPU) time and memory bandwidth required for such decompression may be large and costly from a computational perspective.
Other existing techniques, relative to existing compression schemes, allow fast single instruction, multiple data (SIMD) operations on compressed values, without first decompressing the data. Such techniques offer a significant improvement on computational load, however, the effect is limited since the remaining computation is still linearly related to the amount of data, e.g., the number of data values, because the number of calculations performed increases proportionately to the number of values.